Tree Data Structure is used to organise data in hierarchical manner.
In this video we discuss about:
node,root,leaf,child,parent,subtree,descendants,ancestors,degree and internal nodes.
This track of the course covers the topic "Trees".
In details, this track will cover:
Objective: The objective of this track is to familiarize the learners with Trees.
Track Content:
Assessment: All Tracks in every week are associated with weekly contests.
Tree Data Structure is used to organise data in hierarchical manner.
In this video we discuss about:
node,root,leaf,child,parent,subtree,descendants,ancestors,degree and internal nodes.
In this video, we discuss applications of Trees:
In Binary Tree every node has at most two children.
In this video, we further discuss the implementation to represent a Binary Tree.
Codes:
Tree Traversal is basically going through every node(key) exactly once.
In this video we briefly discuss:
Types of Tree Traversal i.e. Breadth-First Search(BFS) and Depth First Search(DFS).
Inorder, preorder and postorder traversals.
Implementation of Inorder Traversal
In this video, we discuss a function that takes root as a parameter, whose return type is void and is supposed to print inorder traversal of the Tree whose nodes are given.
Codes:
Implementation of Preorder Traversal
In this video, we discuss a function that takes root as a parameter, whose return type is void and is supposed to print Preorder traversal of the Tree whose nodes are given.
Codes:
Implementation of Postorder Traversal
In this video, we discuss a function that takes root as a parameter, whose return type is void and is supposed to print Postorder traversal of the Tree whose nodes are given.
Codes:
Height of Binary Tree is the number of nodes between the longest path from root to leaf node(including the root and leaf node).
In this video we discuss about a recursive function that takes root of the tree and returns the height of the Binary Tree.
Codes:
Nodes at distance k from the root are basically the nodes at (k+1)th level of the Binary Tree.
In this video, we discuss a function that takes root and k as a parameter, whose return type is void and is supposed to print the nodes at distance k from the root.
Codes:
Level order traversal of a tree is breadth first traversal of binary tree.
In this video we will discuss about a function that takes root as a parameter, doesn’t returns anything and prints the level order traversal in a single line.we implement this function using queue datastructure.
Codes:
In Level Order Traversal Line by Line, we print the nodes at each level separately in a new line.
In this video we discuss:
A function that takes root as a parameter, doesn’t return anything and prints the level order traversal line by line by using method-1.
In method-1, we implement this function using a single loop.
Codes:
In Level Order Traversal Line by Line, we print the nodes at each level seperately in a new line.
In this video we discuss:
A function that takes root as a parameter, doesn’t return anything and prints the level order traversal line by line by using method-2.
In method-2, we implement this function using nested loops.
Codes:
Size of Binary Tree is the total numbers of nodes present in that Tree.
In this video, we discuss a recursive function that takes root as a parameter and is supposed to return the size of the Tree whose nodes are given.
Codes:
Largest node(key) in a Tree is the maximum of the Tree.
In this video, we discuss a recursive function that takes the root of a binary Tree and returns the maximum of the Tree.
Codes:
To Print Left View of Binary Tree we need to print the leftmost node at every level of the Binary Tree.
In this video we discuss two methods to print left view of a given Binary Tree.In Method-1 we use Recursive method whereas in Method-2 we use the Iterative method approach by using queue datastructure.
Codes:
Children Sum Property is a property in which the sum of values of the left child and right child should be equal to the value of their node if both children are present. Else if only one child is present then the value of the child should be equal to its node value.
In this video, we discuss a recursive function that takes the root node as a parameter and returns TRUE if the Tree follows C.S.P. and FALSE if the Tree does not follow C.S.P.
Code:
In a Balanced Binary Tree for every node, the difference between heights of left subtree and right subtree should not be more than one.
In this video we discuss two solutions (one with time complexity of O(n^2) and another with time complexity of O(n) ) to check whether a Tree is Balanced or not.
Codes:
Maximum Width of Binary tree is the maximum number of nodes present in a level of the Tree.
In this video, we discuss a function that takes the root of a Binary Tree and returns the maximum width of the Binary Tree.
Hint:- we use level order traversal line by line logic to find maximum width of the Binary Tree.
Codes:
In this video we discuss:
Inorder conversion of Binary Tree to Doubly Linked List.
A function that takes root of a Binary Tree and converts it into a Doubly linked list.
Hint:- we need to do the inorder traversal of the Tree and while doing inorder traversal we can simply maintain a previous pointer or reference of the previously traversed node. And change right child of the previous node to current node and left child of current node as previous.
Codes:
This video discusses the Construction of a Binary Tree from Inorder and Preorder traversal.
Codes:
This video discusses the method of Tree Traversal in Spiral Form.
Codes:
Three method of finding diameter of a Binary Tree are discussed.
Codes:
Introduction to LCA (Lowest Common Ancestor) problem and a O(n) solution to the problem.
Codes:
An efficient solution is discussed in this video. The solution does only one traversal of binary tree, but assumes that both keys exist in the binary tree.
Codes:
We are given a binary tree and a leaf node, we need to find time to burn the Binary Tree if we burn the given leaf at 0-th second.
Codes:
Given a binary tree, our task is to count toal nodes. Two methods are discussed here, naive method which is O(n). And an efficient method which is O(Log n * Log n)
Codes:
This video talks about serialize and deserialize a binary tree. It discusses preorder traversal based approach.
Codes:
The video discisses stack based inorder traversal.
A O(n) extra space and O(n) time solution is discussed.
A O(h) extra space and O(n) time solution is discussed.
A Tree is a non-linear data structure where each node is connected to a number of nodes with the help of pointers or references.

A Tree is said to be a Binary Tree if all of its nodes have atmost 2 children. That is, all of its node can have either no child, 1 child, or 2 child nodes.

L <= 2l-1 [From Point 1]
l = Log2L + 1
where l is the minimum number of levels.
L = T + 1
Where L = Number of leaf nodes
T = Number of internal nodes with two children
In a Full Binary, the number of leaf nodes is number of internal nodes plus 1.
A Perfect Binary Tree of height h (where height is the number of nodes on the path from the root to leaf) has 2h – 1 node.![]()

Algorithm Inorder(tree)Example: Inorder traversal for the above-given tree is 4 2 5 1 3.
1. Traverse the left subtree, i.e.,
call Inorder(left->subtree)
2. Visit the root.
3. Traverse the right subtree, i.e.,
call Inorder(right->subtree)
Algorithm Preorder(tree)Example: Preorder traversal for the above-given tree is 1 2 4 5 3.
1. Visit the root.
2. Traverse the left subtree, i.e.,
call Preorder(left-subtree)
3. Traverse the right subtree, i.e.,
call Preorder(right-subtree)
Algorithm Postorder(tree)Example: Postorder traversal for the above-given Tree is 4 5 2 3 1.
1. Traverse the left subtree, i.e.,
call Postorder(left-subtree)
2. Traverse the right subtree, i.e.,
call Postorder(right-subtree)
3. Visit the root.
// C++ program for different tree traversals
#include <iostream>
using namespace std;
/* A binary tree node has data, pointer to left child
and a pointer to right child */
struct Node
{
int data;
struct Node* left, *right;
Node(int data)
{
this->data = data;
left = right = NULL;
}
};
// Function to print the postorder traversal
// of a Binary Tree
void printPostorder(struct Node* node)
{
if (node == NULL)
return;
// first recur on left subtree
printPostorder(node->left);
// then recur on right subtree
printPostorder(node->right);
// now deal with the node
cout << node->data << " ";
}
// Function to print the Inorder traversal
// of a Binary Tree
void printInorder(struct Node* node)
{
if (node == NULL)
return;
/* first recur on left child */
printInorder(node->left);
/* then print the data of node */
cout << node->data << " ";
/* now recur on right child */
printInorder(node->right);
}
// Function to print the PreOrder traversal
// of a Binary Tree
void printPreorder(struct Node* node)
{
if (node == NULL)
return;
/* first print data of node */
cout << node->data << " ";
/* then recur on left sutree */
printPreorder(node->left);
/* now recur on right subtree */
printPreorder(node->right);
}
// Driver Code
int main()
{
// Contrust the Tree
// 1
// / \
// 2 3
// / \
// 4 5
struct Node *root = new Node(1);
root->left = new Node(2);
root->right = new Node(3);
root->left->left = new Node(4);
root->left->right = new Node(5);
cout << "Preorder traversal of binary tree is \n";
printPreorder(root);
cout << "\nInorder traversal of binary tree is \n";
printInorder(root);
cout << "\nPostorder traversal of binary tree is \n";
printPostorder(root);
return 0;
}
// Java program for different tree traversals
/* Class containing left and right child of current
node and key value*/
class Node
{
int key;
Node left, right;
public Node(int item)
{
key = item;
left = right = null;
}
}
class BinaryTree
{
// Root of Binary Tree
Node root;
BinaryTree()
{
root = null;
}
// Method to print postorder traversal.
void printPostorder(Node node)
{
if (node == null)
return;
// first recur on left subtree
printPostorder(node.left);
// then recur on right subtree
printPostorder(node.right);
// now deal with the node
System.out.print(node.key + " ");
}
// Method to print inorder traversal
void printInorder(Node node)
{
if (node == null)
return;
/* first recur on left child */
printInorder(node.left);
/* then print the data of node */
System.out.print(node.key + " ");
/* now recur on right child */
printInorder(node.right);
}
// Method to print preorder traversal
void printPreorder(Node node)
{
if (node == null)
return;
/* first print data of node */
System.out.print(node.key + " ");
/* then recur on left sutree */
printPreorder(node.left);
/* now recur on right subtree */
printPreorder(node.right);
}
// Wrappers over above recursive functions
void printPostorder() { printPostorder(root); }
void printInorder() { printInorder(root); }
void printPreorder() { printPreorder(root); }
// Driver method
public static void main(String[] args)
{
BinaryTree tree = new BinaryTree();
tree.root = new Node(1);
tree.root.left = new Node(2);
tree.root.right = new Node(3);
tree.root.left.left = new Node(4);
tree.root.left.right = new Node(5);
System.out.println("Preorder traversal of binary tree is ");
tree.printPreorder();
System.out.println("\nInorder traversal of binary tree is ");
tree.printInorder();
System.out.println("\nPostorder traversal of binary tree is ");
tree.printPostorder();
}
}Preorder traversal of binary tree is
1 2 4 5 3
Inorder traversal of binary tree is
4 2 5 1 3
Postorder traversal of binary tree is
4 5 2 3 1


// C++ program to print level order traversal
// of a Tree
#include <iostream>
#include <queue>
using namespace std;
// A Binary Tree Node
struct Node
{
int data;
struct Node *left, *right;
};
// Utility function to create a new tree node
Node* newNode(int data)
{
Node *temp = new Node;
temp->data = data;
temp->left = temp->right = NULL;
return temp;
}
// Function to print Level Order Traversal
// of the Binary Tree
void printLevelOrder(Node *root)
{
// Base Case
if (root == NULL) return;
// Create an empty queue for
// level order tarversal
queue<Node *> q;
// Enqueue Root and initialize height
q.push(root);
while (q.empty() == false)
{
// Print front of queue and remove
// it from queue
Node *node = q.front();
cout << node->data << " ";
q.pop();
/* Enqueue left child */
if (node->left != NULL)
q.push(node->left);
/* Enqueue right child */
if (node->right != NULL)
q.push(node->right);
}
}
// Driver Code
int main()
{
// Create the following Binary Tree
// 1
// / \
// 2 3
// / \
// 4 5
Node *root = newNode(1);
root->left = newNode(2);
root->right = newNode(3);
root->left->left = newNode(4);
root->left->right = newNode(5);
cout << "Level Order traversal of binary tree is \n";
printLevelOrder(root);
return 0;
}
// Iterative Queue based Java program to do
// level order traversal of Binary Tree
import java.util.Queue;
import java.util.LinkedList;
/* Class to represent Tree node */
class Node {
int data;
Node left, right;
public Node(int item) {
data = item;
left = null;
right = null;
}
}
/* Class to print Level Order Traversal */
class BinaryTree {
Node root;
/* Given a binary tree. Print its nodes in
level order using array for implementing queue */
void printLevelOrder()
{
Queue<Node> queue = new LinkedList<Node>();
queue.add(root);
while (!queue.isEmpty())
{
Node tempNode = queue.poll();
System.out.print(tempNode.data + " ");
/* Enqueue left child */
if (tempNode.left != null) {
queue.add(tempNode.left);
}
/* Enqueue right child */
if (tempNode.right != null) {
queue.add(tempNode.right);
}
}
}
// Driver Code
public static void main(String args[])
{
// Create the following Binary Tree
// 1
// / \
// 2 3
// / \
// 4 5
BinaryTree tree_level = new BinaryTree();
tree_level.root = new Node(1);
tree_level.root.left = new Node(2);
tree_level.root.right = new Node(3);
tree_level.root.left.left = new Node(4);
tree_level.root.left.right = new Node(5);
System.out.println("Level order traversal " +
"of binary tree is - ");
tree_level.printLevelOrder();
}
} 1 2 3 4 5

// C++ program to insert element in binary tree
#include <iostream>
#include <queue>
using namespace std;
// A binary tree node
struct Node {
int key;
struct Node* left, *right;
};
// Utility function to create a new Node
struct Node* newNode(int key)
{
struct Node* temp = new Node;
temp->key = key;
temp->left = temp->right = NULL;
return temp;
};
// Function to print InOrder traversal
// of a Binary Tree
void inorder(struct Node* temp)
{
if (!temp)
return;
inorder(temp->left);
cout << temp->key << " ";
inorder(temp->right);
}
// Function to insert a new element in a Binary Tree
void insert(struct Node* temp, int key)
{
queue<struct Node*> q;
q.push(temp);
// Do level order traversal until we find
// an empty place.
while (!q.empty()) {
struct Node* temp = q.front();
q.pop();
if (!temp->left) {
temp->left = newNode(key);
break;
} else
q.push(temp->left);
if (!temp->right) {
temp->right = newNode(key);
break;
} else
q.push(temp->right);
}
}
// Driver code
int main()
{
// Create the following Binary Tree
// 10
// / \
// 11 9
// / \
// 7 8
struct Node* root = newNode(10);
root->left = newNode(11);
root->left->left = newNode(7);
root->right = newNode(9);
root->right->left = newNode(15);
root->right->right = newNode(8);
cout << "Inorder traversal before insertion:";
inorder(root);
int key = 12;
insert(root, key);
cout << endl;
cout << "Inorder traversal after insertion:";
inorder(root);
return 0;
}
// Java program to insert element in binary tree
import java.util.LinkedList;
import java.util.Queue;
public class GFG {
// Binary Tree Node
static class Node {
int key;
Node left, right;
// constructor
Node(int key){
this.key = key;
left = null;
right = null;
}
}
static Node root;
static Node temp = root;
// Function to perform InOrder traversal
// of the Binary Tree
static void inorder(Node temp)
{
if (temp == null)
return;
inorder(temp.left);
System.out.print(temp.key+" ");
inorder(temp.right);
}
// Function to insert a new element in the
// Binary Tree
static void insert(Node temp, int key)
{
Queue<Node> q = new LinkedList<Node>();
q.add(temp);
// Do level order traversal until we find
// an empty place.
while (!q.isEmpty()) {
temp = q.peek();
q.remove();
if (temp.left == null) {
temp.left = new Node(key);
break;
} else
q.add(temp.left);
if (temp.right == null) {
temp.right = new Node(key);
break;
} else
q.add(temp.right);
}
}
// Driver code
public static void main(String args[])
{
// Create the following Binary Tree
// 10
// / \
// 11 9
// / \
// 7 8
root = new Node(10);
root.left = new Node(11);
root.left.left = new Node(7);
root.right = new Node(9);
root.right.left = new Node(15);
root.right.right = new Node(8);
System.out.print( "Inorder traversal before insertion: ");
inorder(root);
int key = 12;
insert(root, key);
System.out.print("\nInorder traversal after insertion: ");
inorder(root);
}
} Inorder traversal before insertion: 7 11 10 15 9 8
Inorder traversal after insertion: 7 11 12 10 15 9 8
Delete 10 in below tree
Output :![]()
Delete 20 in below tree
Output :

// C++ program to delete element in binary tree
#include <bits/stdc++.h>
using namespace std;
// Binary Tree Node
struct Node
{
int key;
struct Node* left, *right;
};
// Utility function to create a new
// Binary Tree Node
struct Node* newNode(int key)
{
struct Node* temp = new Node;
temp->key = key;
temp->left = temp->right = NULL;
return temp;
};
// Function to perform Inorder Traversal
void inorder(struct Node* temp)
{
if (!temp)
return;
inorder(temp->left);
cout << temp->key << " ";
inorder(temp->right);
}
// Function to delete the given deepest node
// (d_node) in binary tree
void deletDeepest(struct Node *root, struct Node *d_node)
{
queue<struct Node*> q;
q.push(root);
// Do level order traversal until last node
struct Node* temp;
while(!q.empty())
{
temp = q.front();
q.pop();
if (temp->right)
{
if (temp->right == d_node)
{
temp->right = NULL;
delete(d_node);
return;
}
else
q.push(temp->right);
}
if (temp->left)
{
if (temp->left == d_node)
{
temp->left=NULL;
delete(d_node);
return;
}
else
q.push(temp->left);
}
}
}
// Function to delete element in binary tree
void deletion(struct Node* root, int key)
{
queue<struct Node*> q;
q.push(root);
struct Node *temp;
struct Node *key_node = NULL;
// Do level order traversal to find deepest
// node(temp) and node to be deleted (key_node)
while (!q.empty())
{
temp = q.front();
q.pop();
if (temp->key == key)
key_node = temp;
if (temp->left)
q.push(temp->left);
if (temp->right)
q.push(temp->right);
}
int x = temp->key;
deletDeepest(root, temp);
key_node->key = x;
}
// Driver code
int main()
{
// Create the following Binary Tree
// 10
// / \
// 11 9
// / \ / \
// 7 12 15 8
struct Node* root = newNode(10);
root->left = newNode(11);
root->left->left = newNode(7);
root->left->right = newNode(12);
root->right = newNode(9);
root->right->left = newNode(15);
root->right->right = newNode(8);
cout << "Inorder traversal before deletion : ";
inorder(root);
int key = 11;
deletion(root, key);
cout << endl;
cout << "Inorder traversal after deletion : ";
inorder(root);
return 0;
}
// Java program to delete element in binary tree
import java.util.LinkedList;
import java.util.Queue;
public class GFG {
// Binary Tree Node
static class Node {
int key;
Node left, right;
// constructor
Node(int key){
this.key = key;
left = null;
right = null;
}
}
static Node root;
static Node temp = root;
// Function to perform Inorder traversal
// of a binary tree
static void inorder(Node temp)
{
if (temp == null)
return;
inorder(temp.left);
System.out.print(temp.key+" ");
inorder(temp.right);
}
// Function to delete the given deepest node
// (d_node) in binary tree
static void deleteDeepest(Node root, Node d_node)
{
Queue<Node> q = new LinkedList<Node>();
q.add(root);
// Do level order traversal until last node
Node temp;
while(!q.isEmpty())
{
temp = q.peek();
q.remove();
if (temp.right!=null)
{
if (temp.right == d_node)
{
temp.right = null;
d_node = null;
return;
}
else
q.add(temp.right);
}
if (temp.left!=null)
{
if (temp.left == d_node)
{
temp.left=null;
d_node = null;
return;
}
else
q.add(temp.left);
}
}
}
// Function to delete element in binary tree
static void deletion(Node root, int key)
{
Queue<Node> q = new LinkedList<Node>();
q.add(root);
Node temp = null;
Node key_node = null;
// Do level order traversal to find deepest
// node(temp) and node to be deleted (key_node)
while (!q.isEmpty())
{
temp = q.peek();
q.remove();
if (temp.key == key)
key_node = temp;
if (temp.left!=null)
q.add(temp.left);
if (temp.right!=null)
q.add(temp.right);
}
int x = temp.key;
deleteDeepest(root, temp);
key_node.key = x;
}
// Driver code
public static void main(String args[])
{
// Create the following Binary Tree
// 10
// / \
// 11 9
// / \ / \
// 7 12 15 8
root = new Node(10);
root.left = new Node(11);
root.left.left = new Node(7);
root.left.right = new Node(12);
root.right = new Node(9);
root.right.left = new Node(15);
root.right.right = new Node(8);
System.out.print( "Inorder traversal before Deletion:");
inorder(root);
int key = 11;
deletion(root, key);
System.out.print("\nInorder traversal after Deletion:");
inorder(root);
}
}
Inorder traversal before Deletion: 7 11 12 10 15 9 8
Inorder traversal after Deletion: 7 8 12 10 15 9
The LCA or Lowest Common Ancestor of any two nodes N1 and N2 is defined as the common ancestor of both the nodes which is closest to them. That is the distance of the common ancestor from the nodes N1 and N2 should be least possible.

Finding LCA
Method 1: The simplest method of finding LCA of two nodes in a Binary Tree is to observe that the LCA of the given nodes will be the last common node in the paths from the root node to the given nodes.// C++ Program for Lowest Common Ancestor
// in a Binary Tree
#include <iostream>
#include <vector>
using namespace std;
// A Binary Tree node
struct Node {
int key;
struct Node *left, *right;
};
// Utility function creates a new binary tree
// node with given key
Node* newNode(int k)
{
Node* temp = new Node;
temp->key = k;
temp->left = temp->right = NULL;
return temp;
}
// Function to find the path from root node to
// given root of the tree, Stores the path in a
// vector path[], returns true if path exists
// otherwise false
bool findPath(Node* root, vector<int>& path, int k)
{
// base case
if (root == NULL)
return false;
// Store this node in path vector.
// The node will be removed if
// not in path from root to k
path.push_back(root->key);
// See if the k is same as root's key
if (root->key == k)
return true;
// Check if k is found in left or right sub-tree
if ((root->left && findPath(root->left, path, k)) ||
(root->right && findPath(root->right, path, k)))
return true;
// If not present in subtree rooted with root,
// remove root from path[] and return false
path.pop_back();
return false;
}
// Function to return LCA if node n1, n2 are
// present in the given binary tree, otherwise
// return -1
int findLCA(Node* root, int n1, int n2)
{
// to store paths to n1 and n2 from the root
vector<int> path1, path2;
// Find paths from root to n1 and root to n1.
// If either n1 or n2 is not present, return -1
if (!findPath(root, path1, n1) || !findPath(root, path2, n2))
return -1;
// Compare the paths to get the first
// different value
int i;
for (i = 0; i < path1.size() && i < path2.size(); i++)
if (path1[i] != path2[i])
break;
return path1[i - 1];
}
// Driver Code
int main()
{
// Let us create the Binary Tree
// as shown in the above diagram
Node* root = newNode(1);
root->left = newNode(2);
root->right = newNode(3);
root->left->left = newNode(4);
root->left->right = newNode(5);
root->right->left = newNode(6);
root->right->right = newNode(7);
cout << "LCA(4, 5) = " << findLCA(root, 4, 5);
cout << "\nLCA(4, 6) = " << findLCA(root, 4, 6);
cout << "\nLCA(3, 4) = " << findLCA(root, 3, 4);
cout << "\nLCA(2, 4) = " << findLCA(root, 2, 4);
return 0;
}
// Java Program for Lowest Common Ancestor
// in a Binary Tree
import java.util.ArrayList;
import java.util.List;
// A Binary Tree node
class Node {
int data;
Node left, right;
Node(int value)
{
data = value;
left = right = null;
}
}
public class FindLCA {
Node root;
private List<Integer> path1 = new ArrayList<>();
private List<Integer> path2 = new ArrayList<>();
// Finds the path from root node to given root of the tree
int findLCA(int n1, int n2)
{
path1.clear();
path2.clear();
return findLCAInternal(root, n1, n2);
}
private int findLCAInternal(Node root, int n1, int n2)
{
if (!findPath(root, n1, path1) || !findPath(root, n2, path2)) {
System.out.println((path1.size() > 0) ?
"n1 is present" : "n1 is missing");
System.out.println((path2.size() > 0) ?
"n2 is present" : "n2 is missing");
return -1;
}
int i;
for (i = 0; i < path1.size() && i < path2.size(); i++) {
if (!path1.get(i).equals(path2.get(i)))
break;
}
return path1.get(i - 1);
}
// Finds the path from root node to given
// root of the tree, Stores the path in a
// vector path[], returns true if path
// exists otherwise false
private boolean findPath(Node root, int n,
List<Integer> path)
{
// base case
if (root == null) {
return false;
}
// Store this node. The node will be removed if
// not in path from root to n.
path.add(root.data);
if (root.data == n) {
return true;
}
if (root.left != null && findPath(root.left, n, path)) {
return true;
}
if (root.right != null && findPath(root.right, n, path)) {
return true;
}
// If not present in subtree rooted with root,
// remove root from path[] and return false
path.remove(path.size() - 1);
return false;
}
// Driver code
public static void main(String[] args)
{
FindLCA tree = new FindLCA();
tree.root = new Node(1);
tree.root.left = new Node(2);
tree.root.right = new Node(3);
tree.root.left.left = new Node(4);
tree.root.left.right = new Node(5);
tree.root.right.left = new Node(6);
tree.root.right.right = new Node(7);
System.out.println("LCA(4, 5): " + tree.findLCA(4, 5));
System.out.println("LCA(4, 6): " + tree.findLCA(4, 6));
System.out.println("LCA(3, 4): " + tree.findLCA(3, 4));
System.out.println("LCA(2, 4): " + tree.findLCA(2, 4));
}
}LCA(4, 5) = 2
LCA(4, 6) = 1
LCA(3, 4) = 1
LCA(2, 4) = 2
// C++ Program to find LCA of n1 and n2 using
// one traversal of Binary Tree
#include <iostream>
using namespace std;
// A Binary Tree Node
struct Node {
struct Node *left, *right;
int key;
};
// Utility function to create a new tree Node
Node* newNode(int key)
{
Node* temp = new Node;
temp->key = key;
temp->left = temp->right = NULL;
return temp;
}
// This function returns pointer to LCA of two given
// values n1 and n2. This function assumes that
// n1 and n2 are present in Binary Tree
struct Node* findLCA(struct Node* root, int n1, int n2)
{
// Base case
if (root == NULL)
return NULL;
// If either n1 or n2 matches with root's key, report
// the presence by returning root (Note that if a key is
// ancestor of other, then the ancestor key becomes LCA
if (root->key == n1 || root->key == n2)
return root;
// Look for keys in left and right subtrees
Node* left_lca = findLCA(root->left, n1, n2);
Node* right_lca = findLCA(root->right, n1, n2);
// If both of the above calls return Non-NULL,
// then one key is present in once subtree and
// other is present in other,
// So this node is the LCA
if (left_lca && right_lca)
return root;
// Otherwise check if left subtree or
// right subtree is LCA
return (left_lca != NULL) ? left_lca : right_lca;
}
// Driver Code
int main()
{
// Let us create binary tree given in the above example
Node* root = newNode(1);
root->left = newNode(2);
root->right = newNode(3);
root->left->left = newNode(4);
root->left->right = newNode(5);
root->right->left = newNode(6);
root->right->right = newNode(7);
cout << "LCA(4, 5) = " << findLCA(root, 4, 5)->key;
cout << "nLCA(4, 6) = " << findLCA(root, 4, 6)->key;
cout << "nLCA(3, 4) = " << findLCA(root, 3, 4)->key;
cout << "nLCA(2, 4) = " << findLCA(root, 2, 4)->key;
return 0;
}
// Java implementation to find lowest common ancestor of
// n1 and n2 using one traversal of binary tree
// Class containing left and right child of current
// node and key value
class Node {
int data;
Node left, right;
public Node(int item)
{
data = item;
left = right = null;
}
}
// Binary Tree Class
public class BinaryTree {
// Root of the Binary Tree
Node root;
Node findLCA(int n1, int n2)
{
return findLCA(root, n1, n2);
}
// This function returns pointer to LCA of two given
// values n1 and n2. This function assumes that n1 and
// n2 are present in Binary Tree
Node findLCA(Node node, int n1, int n2)
{
// Base case
if (node == null)
return null;
// If either n1 or n2 matches with root's key, report
// the presence by returning root (Note that if a key is
// ancestor of other, then the ancestor key becomes LCA
if (node.data == n1 || node.data == n2)
return node;
// Look for keys in left and right subtrees
Node left_lca = findLCA(node.left, n1, n2);
Node right_lca = findLCA(node.right, n1, n2);
// If both of the above calls return Non-NULL, then one key
// is present in once subtree and other is present in other,
// So this node is the LCA
if (left_lca != null && right_lca != null)
return node;
// Otherwise check if left subtree or right subtree is LCA
return (left_lca != null) ? left_lca : right_lca;
}
// Driver Code
public static void main(String args[])
{
BinaryTree tree = new BinaryTree();
tree.root = new Node(1);
tree.root.left = new Node(2);
tree.root.right = new Node(3);
tree.root.left.left = new Node(4);
tree.root.left.right = new Node(5);
tree.root.right.left = new Node(6);
tree.root.right.right = new Node(7);
System.out.println("LCA(4, 5) = " + tree.findLCA(4, 5).data);
System.out.println("LCA(4, 6) = " + tree.findLCA(4, 6).data);
System.out.println("LCA(3, 4) = " + tree.findLCA(3, 4).data);
System.out.println("LCA(2, 4) = " + tree.findLCA(2, 4).data);
}
}
LCA(4, 5) = 2nLCA(4, 6) = 1nLCA(3, 4) = 1nLCA(2, 4) = 2

1 + height of left subtree of nd + height of right subtree of nd
Diameter = maximum(lDiameter, rDiameter, 1 + lHeight + rHeight)
Where,
lDiameter = Diameter of left subtree
rDiameter = Diameter of right subtree
lHeight = Height of left subtree
rHeight = Height of right subtree
// C++ program to calculate Diameter of a Binary Tree
#include <bits/stdc++.h>
using namespace std;
// Binary Tree Node
struct node
{
int data;
struct node* left, *right;
};
// Function to create a new node of tree
// and returns pointer
struct node* newNode(int data);
// Function to Compute height of a tree
int height(struct node* node);
// Function to get diameter of a binary tree
int diameter(struct node * tree)
{
/* base case where tree is empty */
if (tree == NULL)
return 0;
/* get the height of left and right sub-trees */
int lheight = height(tree->left);
int rheight = height(tree->right);
/* get the diameter of left and right sub-trees */
int ldiameter = diameter(tree->left);
int rdiameter = diameter(tree->right);
/* Return max of following three
1) Diameter of left subtree
2) Diameter of right subtree
3) Height of left subtree + height of right subtree + 1 */
return max(lheight + rheight + 1, max(ldiameter, rdiameter));
}
/* UTILITY FUNCTIONS TO TEST diameter() FUNCTION */
/* The function Compute the "height" of a tree. Height is the
number f nodes along the longest path from the root node
down to the farthest leaf node.*/
int height(struct node* node)
{
/* base case tree is empty */
if(node == NULL)
return 0;
/* If tree is not empty then height = 1 + max of left
height and right heights */
return 1 + max(height(node->left), height(node->right));
}
/* Helper function that allocates a new node with the
given data and NULL left and right pointers. */
struct node* newNode(int data)
{
struct node* node = (struct node*)
malloc(sizeof(struct node));
node->data = data;
node->left = NULL;
node->right = NULL;
return(node);
}
// Driver Code
int main()
{
/* Constructed binary tree is
1
/ \
2 3
/ \
4 5
*/
struct node *root = newNode(1);
root->left = newNode(2);
root->right = newNode(3);
root->left->left = newNode(4);
root->left->right = newNode(5);
cout<<"Diameter of the given binary tree is "<<diameter(root);
return 0;
}
// Recursive optimized Java program to find the diameter of a
// Binary Tree
/* Class containing left and right child of current
node and key value*/
class Node
{
int data;
Node left, right;
public Node(int item)
{
data = item;
left = right = null;
}
}
/* Class to print the Diameter */
class BinaryTree
{
Node root;
/* Method to calculate the diameter and return it to main */
int diameter(Node root)
{
/* base case if tree is empty */
if (root == null)
return 0;
/* get the height of left and right sub trees */
int lheight = height(root.left);
int rheight = height(root.right);
/* get the diameter of left and right subtrees */
int ldiameter = diameter(root.left);
int rdiameter = diameter(root.right);
/* Return max of following three
1) Diameter of left subtree
2) Diameter of right subtree
3) Height of left subtree + height of right subtree + 1 */
return Math.max(lheight + rheight + 1,
Math.max(ldiameter, rdiameter));
}
/* A wrapper over diameter(Node root) */
int diameter()
{
return diameter(root);
}
/*The function Compute the "height" of a tree. Height is the
number f nodes along the longest path from the root node
down to the farthest leaf node.*/
static int height(Node node)
{
/* base case tree is empty */
if (node == null)
return 0;
/* If tree is not empty then height = 1 + max of left
height and right heights */
return (1 + Math.max(height(node.left), height(node.right)));
}
public static void main(String args[])
{
/* creating a binary tree and entering the nodes */
BinaryTree tree = new BinaryTree();
tree.root = new Node(1);
tree.root.left = new Node(2);
tree.root.right = new Node(3);
tree.root.left.left = new Node(4);
tree.root.left.right = new Node(5);
System.out.println("The diameter of given binary tree is : "
+ tree.diameter());
}
}Diameter of the given binary tree is 4
Consider the Below Binary Tree:
Left View of above Tree will be: 1, 2, 4
Right View of above Tree will be: 1, 3, 7
Top View of above Tree will be: 4, 2, 1, 3, 7
Bottom View of above Tree will be: 4, 5, 6, 7
//Complete Code
// Function to print the left view of the binary tree
void leftViewUtil(Node root)
{
// Declare a queue for Level order Traversal
queue<Node*> q;
if (root == NULL)
return;
// Push root
q.push(root);
// Delimiter
q.push(NULL);
while (!q.empty()) {
Node* temp = q.front();
if (temp) {
// Prints first node
// of each level
print temp->data;
// Push children of all nodes at
// current level
while (q.front() != NULL) {
// If left child is present
// push into queue
if (temp->left)
q.push(temp->left);
// If right child is present
// push into queue
if (temp->right)
q.push(temp->right);
// Pop the current node
q.pop();
temp = q.front();
}
// Push delimiter
// for the next level
q.push(NULL);
}
// Pop the delimiter of
// the previous level
q.pop();
}
} // Complete Code
// Structure of binary tree
// Binary Tree node is modified to contain
// an extra parameter hd, which is the
// horizontal distance of the node from root node.
struct Node
{
Node * left;
Node* right;
int hd;
int data;
};
// Function to print the topView of
// the binary tree
void topview(Node* root)
{
if(root==NULL)
return;
queue<Node*>q;
map<int,int> m;
int hd=0;
root->hd = hd;
// push node and horizontal distance to queue
q.push(root);
print "The top view of the tree is : ";
while(q.size())
{
hd = root->hd;
// Check if any node with this horizontal distance
// is encontered yet or not.
// If not insert, current node's data to Map
if(m.count(hd)==0)
m[hd]=root->data;
// Push the left child with its
// horizontal distance to queue
if(root->left)
{
root->left->hd=hd-1;
q.push(root->left);
}
// Push the right child with its
// horizontal distance to queue
if(root->right)
{
root->right->hd=hd+1;
q.push(root->right);
}
q.pop();
root=q.front();
}
// Print the map as it stores the nodes
// appearing in the Top View
for(auto i=m.begin();i!=m.end();i++)
{
cout<<i->second<<" ";
}
}
Solution - The idea is to do something similar to vertical Order Traversal. Like vertical Order Traversal, we need to put nodes of same horizontal distance together. We do a level order traversal so that the topmost node at a horizontal node is visited before any other node of same horizontal distance below it. Hashing is used to check if a node at a given horizontal distance is seen or not.
Top view of the above binary tree is
4 2 1 3 7
Top view of the above binary tree is
2 1 3 6
// function should print the topView of
// the binary tree
void topview(Node* root)
{
if(root==NULL)
return;
queue < Node* > q
map < int,int > m
int hd=0
root->hd=hd
// push node and horizontal distance to queue
q.push(root);
while(!q.empty())
{
hd=root->hd
// check whether node at hd distance seen or not
if(m.find(hd)==false)
m[hd]=root->data
if(root->left)
{
root->left->hd=hd-1
q.push(root->left)
}
if(root->right)
{
root->right->hd=hd+1
q.push(root->right)
}
q.pop()
root=q.front()
}
for(it=m.begin();it!=m.end();it++)
{
print(it->second)
}
}

int diameter(struct node *root, int* height)
{
/* lh --> Height of left subtree
rh --> Height of right subtree */
int lh = 0, rh = 0
/* ldiameter --> diameter of left subtree
rdiameter --> Diameter of right subtree */
int ldiameter = 0, rdiameter = 0
if(root == NULL)
{
*height = 0
return 0 /* diameter is also 0 */
}
/* Get the heights of left and right subtrees in lh and rh
And store the returned values in ldiameter and ldiameter */
ldiameter = diameter(root->left, &lh)
rdiameter = diameter(root->right, &rh)
/* Height of current node is max of heights of left and
right subtrees plus 1*/
*height = max(lh, rh) + 1
return max(lh + rh + 1, max(ldiameter, rdiameter))
}
// function to convert binary tree to it's mirror
void mirror(struct Node* node)
{
if (node == NULL)
return
else
{
struct Node* temp
/* Recur for subtrees */
mirror(node->left)
mirror(node->right)
/* swap the pointers in this node */
temp = node->left
node->left = node->right
node->right = temp
}
}
Solution - The idea is to do inorder traversal of the binary tree. While doing inorder traversal, keep track of the previously visited node in a variable say prev. For every visited node, make it next of prev and previous of this node as prev.// A simple recursive function to convert a given Binary tree to Doubly
// Linked List
// root --> Root of Binary Tree
// head --> Pointer to head node of created doubly linked list
void BinaryTree2DoubleLinkedList(node *root, node **head)
{
// Base case
if (root == NULL)
return
// Initialize previously visited node as NULL. This is
// static so that the same value is accessible in all recursive
// calls
static node* prev = NULL
// Recursively convert left subtree
BinaryTree2DoubleLinkedList(root->left, head)
// Now convert this node
if (prev == NULL)
*head = root
else
{
root->left = prev
prev->right = root
}
prev = root
// Finally convert right subtree
BinaryTree2DoubleLinkedList(root->right, head)
}
A | Every binary tree is either complete or full. |
B | Every complete binary tree is also a full binary tree. |
C | Every full binary tree is also a complete binary tree. |
D | No binary tree is both complete and full. |
E | None of the above |